/**
 * @param {string[]} words
 * @return {string}
 */
export var alienOrder = function (words) {
  let graph = new Map() // 记录图
  for (const c of words[0]) {
    if (!graph.has(c)) {
      graph.set(c, [])
    }
  }
  let indegree = new Map()

  for (let i = 1; i < words.length; i++) {
    for (const c of words[i]) {
      if (!graph.has(c)) {
        graph.set(c, [])
      }
    }
    // addToGraph
    const [before, after] = [words[i - 1], words[i]]
    let j = 0,
      len = Math.min(before.length, after.length)
    while (j < len) {
      if (before[j] !== after[j]) {
        graph.get(before[j]).push(after[j])
        indegree.set(after[j], (indegree.get(after[j]) || 0) + 1)
        break
      }
      j++
    }
    if (j === len && before.length > after.length) {
      return ''
    }
    // addToGraph(words[i - 1], words[i])
  }

  let queue = []
  // 把入度为0的字符放入队列
  for (const k of graph.keys()) {
    if (!indegree.has(k)) {
      queue.push(k)
    }
  }
  let ans = ''
  while (queue.length) {
    const k = queue.shift()
    ans += k
    for (const c of graph.get(k)) {
      indegree.set(c, indegree.get(c) - 1)
      if (!indegree.get(c)) {
        queue.push(c)
      }
    }
  }
  return ans.length === graph.size ? ans : ''
}
